Louvain 社区发现算法

它用于从图结构中发现连接紧密的"社区".
对于一个图结构, 定义它的 模块度 为 $$Q=\frac{1}{2m}\sum _{i,j}[A_{ij}-\frac{k_i{k}_j}{2m}]\delta (c_i,c_j).$$

• ${\displaystyle m}$ 是边的总权重, ${\displaystyle A_{ij}}$ 是 ${\displaystyle i,j}$ 的权重
• ${\displaystyle k_i,j_j}$ 是 ${\displaystyle i,j}$ 的度(边权重之和)
• ${\displaystyle c_i,c_j}$ 是 ${\displaystyle i,j}$ 所属社区; ${\displaystyle \delta (c_i,c_j)}$ 代表 ${\displaystyle i,j}$ 是否在一个社区

可以认为 Louvain 是一种图上面的聚类算法.

• 初始化：算法开始时，每个节点都自成一个独立的社区。
• 迭代优化过程（重复执行直到Q不再增加）：
  • 阶段一：节点移动与模块度优化
    • 算法会遍历图中的每一个节点. 对于当前节点 ${\displaystyle i}$, 算法会尝试将它从它当前的社区中“拿出来”, 然后依次放入它的每一个邻居节点所在的社区.
    • 每尝试放入一个邻居社区，就计算一次模块度的增益.
    • 最后, 将节点 ${\displaystyle i}$ 放入那个能让模块度增益最大的邻居社区中. 如果没有任何移动能带来正增益，节点 ${\displaystyle i}$ 就留在原社区
    • 这个过程会对所有节点重复进行，直到没有节点可以被移动来增加模块度为止。阶段一结束
  • 阶段二：社区聚合（重建网络）
    • 将阶段一发现的所有社区，各自聚合成一个新的“超级节点”。
    • 原社区内部的边，权重会累加成为新“超级节点”的**自环（self-loop）**的权重。
    • 原社区之间的边，权重会成为新的“超级节点”之间的边的权重。
    • 这样，我们就得到了一个规模更小、以社区为节点的新图。
  • 返回阶段一：在这个新的聚合图上，重新执行阶段一的节点移动过程。